

# 合并K个升序列表


class Solution:

    def mergeKLists(self, lists):

        if not lists:
            return
        
        def merge(l1, l2):

            if not l1:
                return l2
            if not l2:
                return l1
            p = res = ListNode(0)
            while l1 and l2:
                if l1.val <= l2.val:

                    p.next = l1
                    l1 = l1.next
                else:
                    p.next = l2
                    l2 = l2.next
                
                p = p.next
            p.next = l1 if l1 else l2

            return res.next
        
        l1 = lists[0]
        # 也可以使用二分法进行合并
        for i in range(1, len(lists)):

            l2 = lists[i]

            l1 = merge(l1, l2)

        
        return l1
            



